package cn.example.demo.common.model.tree.factory;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.*;

/**
 * <p>
 * 默认递归工具类，用于遍历有父子关系的节点，例如菜单树，字典树等等
 * </p>
 *
 * @author Lizuxian
 * @create 2021/8/26 23:11
 */
@Data
@NoArgsConstructor
@AllArgsConstructor
public class DefaultTreeBuildFactory<T extends AbstractTreeNode> implements AbstractTreeBuildFactory<T> {
    /**
     * 默认顶级节点ID
     */
    public static final Integer ROOT_NODE = -1;

    /**
     * 顶级节点的父节点id(默认-1)
     */
    private String rootParentId = "-1";

    @Override
    public List<T> doTreeBuild(List<T> nodes) {
        // 将每个节点的构造一个子树
        for (T treeNode : nodes) {
            // 过滤【节点与父节点指向同一个节点】的情况，防止遍历树冲突
            if (!treeNode.getNodeId().equals(treeNode.getNodeParentId())) {
                this.buildChildNodes(nodes, treeNode, new ArrayList<>());
            }
        }

        // 只保留上级是根节点的节点，也就是只留下所有一级节点
        ArrayList<T> results = new ArrayList<>();
        for (T node : nodes) {
            if (node.getNodeParentId().equals(rootParentId)) {
                results.add(node);
            }
        }

        return results;
    }

    @Override
    public List<T> flattenParents(List<T> nodes) {
        Set<String> finishNodeSet = new HashSet<>();
        for (T treeNode : nodes) {
            // 过滤【节点与父节点指向同一个节点】的情况，防止遍历树冲突
            if (!treeNode.getNodeId().equals(treeNode.getNodeParentId())) {
                this.doFlattenParents(nodes, treeNode, new ArrayList<>(), finishNodeSet);
                // 记录已处理过的节点，防止重复处理
                finishNodeSet.add(treeNode.getNodeId());
            }
        }

        return nodes;
    }

    @Override
    public List<T> flattenChildren(List<T> nodes) {
        for (T treeNode : nodes) {
            // 过滤【节点与父节点指向同一个节点】的情况，防止遍历树冲突
            if (!treeNode.getNodeId().equals(treeNode.getNodeParentId())) {
                this.doFlattenChildren(nodes, treeNode, new ArrayList<>());
            }
        }

        return nodes;
    }

    /**
     * 查询子节点的集合
     *
     * @param totalNodes     所有节点的集合
     * @param node           被查询节点的id
     * @param childNodeLists 被查询节点的子节点集合
     */
    private void buildChildNodes(List<T> totalNodes, T node, List<T> childNodeLists) {
        if (totalNodes == null || node == null) {
            return;
        }

        List<T> nodeSubLists = getSubChildsLevelOne(totalNodes, node);

        for (T nodeSubList : nodeSubLists) {
            buildChildNodes(totalNodes, nodeSubList, new ArrayList<>());
        }

        childNodeLists.addAll(nodeSubLists);
        node.setChildrenNodes(childNodeLists);
    }

    /**
     * 获取子一级节点的集合
     *
     * @param list 所有节点的集合
     * @param node 被查询节点的model
     */
    private List<T> getSubChildsLevelOne(List<T> list, T node) {
        List<T> nodeList = new ArrayList<>();
        for (T nodeItem : list) {
            if (nodeItem.getNodeParentId().equals(node.getNodeId())) {
                nodeList.add(nodeItem);
            }
        }
        return nodeList;
    }

    /**
     * 平铺展开所有父节点
     *
     * @param totalNodes      所有节点的集合
     * @param node            被查询节点的id
     * @param parentNodeLists 被查询节点的父节点集合
     */
    private void doFlattenParents(List<T> totalNodes, T node, List<T> parentNodeLists, Set<String> finishNodeSet) {
        for (T nodeItem : totalNodes) {
            if (node.getNodeParentId().equals(nodeItem.getNodeId())) {
                parentNodeLists.add(nodeItem);
                // 递归
                if (!ROOT_NODE.toString().equals(nodeItem.getNodeParentId())) {
                    doFlattenParents(totalNodes, nodeItem, parentNodeLists, finishNodeSet);
                }
            }
        }

        // 已处理过的节点不能重复赋值，若当前节点某字段依赖自身，会造成循环引用（递归错误）
        if (!finishNodeSet.contains(node.getNodeId())) {
            node.setParentsNodes(parentNodeLists);
        }
    }

    /**
     * 平铺展开所有子节点
     *
     * @param totalNodes     所有节点的集合
     * @param node           被查询节点的id
     * @param childNodeLists 被查询节点的父节点集合
     */
    private void  doFlattenChildren(List<T> totalNodes, T node, List<T> childNodeLists) {
        LinkedList<T> linkedList = new LinkedList<>();
        linkedList.add(node);

        while (!linkedList.isEmpty()) {
            // 出栈
            T t = linkedList.poll();
            // 排除自身
            if (!t.getNodeId().equals(node.getNodeId())) {
                childNodeLists.add(t);
            }
            // 遍历判断是否还有下一层节点，若有则压栈
            for (T nodeItem : totalNodes) {
                if (t.getNodeId().equals(nodeItem.getNodeParentId())) {
                    linkedList.push(nodeItem);
                }
            }
        }

        node.setChildrenNodes(childNodeLists);
    }
}
